// Paulo Kaique Paiva Brasil    matrícula 347203
// Victor Temóteo Pinto         matrícula 347220

#include <math.h>
#include <stdio.h>

struct No{                                                                      //Definição do nó da Lista Encadeada que conterá a rota
    int num;
    
    struct No *prev;
    struct No *next;
};

typedef struct No cel;

int **m;                                                                        //Matriz das cidades, onde [p][0] é a coordenada x do ponto p e [x][1] é a y
int tam;                                                                        //Numero de cidades da entrada
int melhor;                                                                     //Tamanho do melhor caminho (dado na entrada)
int caminho;                                                                    //Tamanho do caminho encontrado
cel *ini;                                                                       //Pontero para o 'inicio' da rota

/**/
void leitura_cid(int x){                                                        // Leitura das  coordenadas das Cidades.
    FILE *cid;
    int i, j;
    char ch, lixo[20];

    if(x == 1) cid = fopen ("Entrada_1.txt", "r");
    if(x == 2) cid = fopen ("Entrada_2.txt", "r");
    if(x == 3) cid = fopen ("Entrada_3.txt", "r");
    if(x == 4) cid = fopen ("Entrada_4.txt", "r");

    if (cid == NULL){
        printf ("Erro na leitura do arquivo.");
    }else{
        
        fgets(lixo, 9, cid);                                                    //Lê "TAMANHO: "
        fscanf (cid, "%d", &tam);                                               //Lê o número de cidades
        ch = getc(cid);                                                         //Lê o "\n"
        fgets(lixo, 8, cid);                                                    //Lê "MELHOR: "
        fscanf (cid, "%d", &melhor);                                            //Lê o melhor caminho existente
        ch = getc(cid);                                                         //Lê o "\n"
        fgets(lixo, 8, cid);                                                    //Lê "N X Y "
        
        m = calloc(tam,sizeof(int));                                            //Aloca dinamicamente a matriz que contém os pontos
        for (i=0;i<tam;i++){
            m[i]=calloc(5,sizeof(int));
        }
    }
    do{
        fscanf (cid, "%d", &i);
        fscanf (cid, "%d", &m[i-1][0]);
        fscanf (cid, "%d", &m[i-1][1]);
        i++;
    }while( i<=tam );
    fclose (cid);
    
}


float eficiencia (){                                                            //Calcula a eficiência da rota em relação com a melhor
    float r;
    r = caminho - melhor;
    r = r/melhor;
    r = r*100;
    
    return ( r );
}


void solucao (){                                                                //Imprime os resultados no arquivo "Solucao.txt"
    FILE *sol;
    cel *cidade;
    float efic;
    
    sol = fopen ("Solucao.txt", "w");
    
    cidade = ini->next;
    printf ("\n\nRota:");
    fprintf(sol, "%d ", ini->num +1);
    while(cidade != ini){
        fprintf(sol, "%d ", cidade->num +1);
        printf (" %d", cidade->num+1);
        cidade = cidade->next;
    }
    
    fprintf (sol, "%d ", caminho);
    printf ("\nCusto: %d ", caminho);
    efic = eficiencia();
    fprintf (sol, "%.2f", efic);
    printf ("\nDesvio: %.2f%%\n\n", efic);
    fclose ( sol );
}


int distancia(int x, int y){                                                    //Calcula a distancia entre dois pontos, passando inteiros
    int d;
    d = sqrt( (m[x][0]-m[y][0])*(m[x][0]-m[y][0]) + (m[x][1]-m[y][1])*(m[x][1]-m[y][1]) );
    
    return(d);
 }


int dist(cel *p, cel *q){                                                       //Calcula a distancia entre dois pontos, passando dois nós
    int i, j;
    i = p->num;
    j = q->num;
    return( distancia(i, j) );
}


cel *criar(int x){                                                              //Função para criar um novo nó
    cel *nova = (cel*) malloc(sizeof(cel));
    nova->num = x;
    return( nova );
}


void ligar(cel *x, cel *y){                                                     //Função para ligar dois nós
    x->next = y;
    y->prev = x;
 }


void insercao(){                                                                //Função usada pra criar a rota inicial
    int i, n=3;
    int bestD;                                                                  //Melhor distancia dentre as cidades na rota até a cidade a ser inserida
    cel *best;                                                                  //Cidade de menor distancia à cidade a ser inserida na rota
    cel *cid1 = criar(0);                                                       //Cria as três primeiras cidades da rota, que são as três primeiras citadas no arquivo
    cel *cid2 = criar(1);
    cel *cid3 = criar(2);
    cel *cidN, *cidComp;                                                        //Cidade a ser inserida e ponteiro para uma cidade da rota que auxilia nas comparações de distancia
    
    ini = cid1;                                                                 //Define a primeira cidade como a "cidade inicial"
    
    ligar(cid1, cid2);                                                          //Faz a ligação entre as três cidades
    ligar(cid2, cid3);
    ligar(cid3, cid1);
    
    caminho = dist(cid1, cid2) + dist(cid2, cid3) + dist(cid3, cid1);           //Inicializa o caminho com a distancia das três primeiras cidades
    
    while( n != tam ){                                                          //Laço que continua até que todas as cidades tenham sido inseridas na rota
        n++;
        
        cidComp = ini->next;                                                    //O Ponteiro inicia com a segunda cidade
        cidN = criar(n-1);                                                      //Cria a cidade a ser inserida
        
        best = ini;                                                             //Colocamos inicialmente a primeira cidade como a mais proxima da cidade a ser inserida
        bestD = dist(cidN, ini);                                                //Colocamos inicialmente a distancia de cidN até a primeira cidade como a menor
        
        for(i=1; i<n-1; i++){                                                   //Acha a cidade mais próxima da que será inserida
            if( dist(cidComp, cidN) < bestD  ){                                 //Ao achar, substitui a cidade de melhor distancia
                best = cidComp;
                bestD = dist(cidComp, cidN);
            }
            cidComp = cidComp->next;
        }
                                                                                //Tendo achado a cidade mais proxima à que será inserida, verifica se é melhor inserir entre a aresta anterior ou posterior daquela
        if(  dist(best->prev, cidN) < dist(best->next, cidN) ){                 //Situação em que a cidade é inserida entre a anterior e a mais proxima
            caminho = caminho - dist(best, best->prev) + dist(best->prev, cidN) + dist(cidN, best); //Atualiza o caminho com relação as trocas 
            ligar(best->prev, cidN);    
            ligar(cidN, best);
        }
        else{                                                                   //Situação em que a cidade é inserida entre a posterior e a mais proxima
            caminho = caminho - dist(best, best->next) + dist(best->next, cidN) + dist(cidN, best); //Atualiza o caminho com relação as trocas
            ligar(cidN, best->next);
            ligar(best, cidN);
        }
    }
}


void swap(cel *A, cel *B, cel *C, cel *D){                                      //Swap liga A com o C e liga o B com o D
    cel *aux, *cid;
    
    caminho = caminho - dist(A,B) - dist(C,D) + dist(A,C) + dist(B,D);          //Atualiza o caminho com relação as trocas
    
    C->next = C->prev;                                                          //Solução de um bug encontrado, mais informações contatar os autores :D
    B->prev = B->next;
    
    ligar(A,C);
    ligar(B,D);
    
    cid = B->prev;
    while( cid != C ){                                                          //Inverte o sentido dos nós entre B e C
        aux = cid->prev;
        cid->prev = cid->next;
        cid->next = aux;
        
        cid = cid->prev;
    }
}


void improving(){                                                               //Verifica os nós apenas até achar uma troca favorável por iteração e faz o cruzamento
    int i, troca;
    cel *A, *B, *C, *D;
    
    do{
        A = ini;
        do{
            troca = 0;
            B = A->next;
            C = B;
            
            for(i=1; i<tam-2; i++){                                             //Laço que verifica se há alguma possivel troca entre laços consecutivos definidos por A - B
                C = C->next;
                D = C->next;
                
                if( (dist(A,B) + dist(C,D)) > (dist(A,C) + dist(B,D)) ){        //Verifica se a distancia à trocar é melhor que a atual
                    swap (A, B, C, D);
                    troca = 1;
                    break;                                                      //Encontrado a troca favorável, faz e sai do laço
                }
            }
            
            A = A->next;            
            if(troca == 1){                                                     //Havendo troca, deve-se sair do loop para iniciar novamente do começo
                break;                                                          
            }
        }while( A != ini );
    } while( troca == 1 );
}


int menu(){                                                                     //Função que imprime o menu
    int x;
    do{
        printf ("Digite 1 para abrir Entrada_1;\nDigite 2 para abrir Entrada_2;\nDigite 3 para abrir Entrada_3;\nDigite 4 para abrir Entrada_4;\n");
        printf ("\nOpção escolhida: ");
        scanf ("%d", &x);
        if ( (x!=1) && (x!=2) && (x!=3) && (x!=4) ){
                printf ("\nOpcao Invalida. Tente denovo:\n\n");
        }
    }while( (x!=1) && (x!=2) && (x!=3) && (x!=4) );
    return (x);
 }



main(){
    int i, x;
    
    x = menu();
    leitura_cid(x);
    insercao();
    improving();
    solucao();
        
    for (i=0;i<tam;i++){
        free (m[i]);
     }
    free(m);
    
    system("PAUSE");
    
    return(0);
}